package com.sort;

import utils.CreateArr;

/**
 * 2)
 * [插入排序]:(从小到大)
 * 1.找到待排数组的第一个元素
 * 2.如果这个元素比它上一个元素小,说明这个元素应该前移,就让前一个元素往后,覆盖掉当前位置,直到前一个元素小于它,说明当前位置就是合适的位置
 * 3.遍历整个数组
 * O(n*n)
 */
public class InsertionSort {

    //版本1 便于理解
    static int[] insertionSort_1(int[] arr) {
        /*这里不需要考虑 arr[0]*/
        //第一步:找到待排数组的第一个元素:即为arr[i]
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];  //记录当前将要插入的值
            for (int j = i; j > 0; j--) {
                //如果这个元素比它上一个元素小,说明这个元素应该前移,就让前一个元素往后,覆盖掉当前位置
                if (arr[j] < arr[j - 1]) {
                    arr[j] = arr[j - 1];
                } else {
                    //直到前一个元素小于它, 说明当前位置就是合适的位置
                    break;
                }
                arr[j - 1] = temp;
            }

        }
        return arr;
    }

    //版本2 简化代码
    static int[] insertionSort_2(int[] arr) {
        //找到待排数组的第一个元素:即为arr[i]
        for (int i = 1; i < arr.length; i++) {
            //既满足可以防止数组下标越界,同时又满足前一个元素大于当前元素,证明还需要向前移动当前元素,进行交换位置的操作
            for (int j = i; j > 0 && arr[j - 1] > arr[j]; j--) {
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
        }
        return arr;
    }

    //版本3 性能优化,将交换操作优化
    static int[] insertionSort_3(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int index = arr[i]; //index表示将要排序的那个元素的值
            int j;  //表示待排序的那个元素应该插入的位置
            for (j = i; j > 0 && arr[j - 1] > index; j--) {
                //满足条件后,这里不进行交换元素操作,而是把前一个元素覆盖在当前位置
                arr[j] = arr[j - 1];
            }
            //循环结束后,表示找到了待排元素应该插入的位置下标为j,这时只需要一次赋值即可
            arr[j] = index;
        }
        return arr;
    }


    public static void main(String[] args) {
        int arr[] = insertionSort_3(CreateArr.createRandomInt(200, 0, 1000));
        System.out.print("\n排序后 : ");
        for (int i : arr) {
            System.out.print(" " + i);
        }
    }

}
